
// quick_sort.h
#ifndef __QUICK_SORT_H__
#define __QUICK_SORT_H__

#include <cstdio>
#include <functional>

template<typename T,typename C>
int partition(T* data, int low, int high, C cmp)
{
    int swap_pos = low - 1;
    T x = data[high];
    for(int i = low; i < high; ++i)
    {
        if(cmp(data[i],x))
        {
            ++swap_pos;
            if(i != swap_pos)
            {
                std::swap(data[i],data[swap_pos]);
            }
        }
    }
    std::swap(data[swap_pos + 1],data[high]);
    return swap_pos + 1;
}

template<typename T,typename C>
void qsort(T* data, int low, int high, C cmp)
{
    if(low >= high)
    {
        return;
    }
    int right_pos = partition(data, low, high, cmp);
    qsort(data, low, right_pos - 1, cmp);
    qsort(data, right_pos + 1, high, cmp);
}

/*
int main()
{
    int a[] = {2,6,20,66,4,99,3,5,7};
    for (int k = 0; k <= 8; k++)
    {
        printf("%d ",a[k]);
    }
    printf("\n");
    qsort(a,0,8,std::less_equal<int>());
    for (int k = 0; k <= 8; k++)
    {
        printf("%d ",a[k]);
    }
    printf("\n");
    return 0;
}
*/

#endif //__QUICK_SORT_H__